package com.nowcoder.Offer.DivideAndRule;

import org.junit.Test;

/**
 * 数组中的逆序对
 */
public class InversePairs {

    public int ans;

    public int[] Megre(int[] arr, int l , int r, int mid){
        int[] temp = new int[r - l + 1];
        int p1 = l, p2 = mid + 1;
        int i = 0;
        while(p1<=mid && p2<=r){
            if(arr[p1] <= arr[p2]){
                temp[i++] = arr[p1++];
            }else{
                temp[i++] = arr[p2++];
                ans += (mid-p1+1)%1000000007;
            }
        }
        while(p1<=mid) temp[i++] = arr[p1++];
        while(p2<=r) temp[i++] = arr[p2++];

        for(int j=0; j<temp.length; j++) arr[l+j] = temp[j];

        return temp;
    }

    public void MegreSort(int[] arr ,int l, int r){
        if(l>=r) return;

        int mid = (l + r) >>> 1;
        MegreSort(arr,l,mid);
        MegreSort(arr,mid+1,r);

        Megre(arr,l,r,mid);
    }

    public int InversePairs(int [] array) {
        ans = 0;
        if (array != null)
            MegreSort(array,0,array.length-1);
        return ans;
    }

    @Test
    public void test(){
        int[] arr = {1,2,3,4,5,6,7,0};
        System.out.println(InversePairs(arr));
        for(int i:arr)
            System.out.print(i+" ");
    }


}

